import java.util.HashMap;
import java.util.Map;

public class MATH {

    public double myPow(double x, int n) {
        if(n==0) return 1;
        else if(n<0){
            if(n==Integer.MIN_VALUE){
                return (1.0/myPow(x,-(n+1)))/x;
            }
            return 1.0 / myPow(x,-n);
        }else {
            double ans = 1.0;
            while(n > 0){
                if((n & 1) == 1)
                    ans *= x;
                x *= x;
                n = n >> 1;//向右移位
            }
            return ans;
        }
    }

    public int mySqrt(int x) {
        int i=0;
        for (i=0;i<x;i++){
            long temp=i*i;
            long temp2=((long)(i+1))*(i+1);
            if ((temp <= x)&&(temp2>x)){
                break;
            }
        }
        return i;
    }

    public boolean isHappy(int n) {
        int hold=n;
        while (n/10>0){
            int change=(int)Math.pow(n%10,2);
            while (n/10!=0){
                n=n/10;
                change=change+(int)Math.pow(n%10,2);
            }
            n=change;
        }
        if(n==1||n==7||n==8)return true;
        else return false;
    }

    public int trailingZeroes(int n) {
        int sum=0;
        while (n>0){
            sum=sum+n/5;
            n/=5;
        }
        return sum;

    }

    public int titleToNumber(String s) {
        int sum=s.charAt(0)-64;
        for (int i=1;i<s.length();i++){
            sum=sum*26+s.charAt(i)-64;
        }
        return sum;
    }

    public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder sb=new StringBuilder();
        if(numerator==0) return "0";
        if(denominator==0) return "";
        int minus=0;
        long num=numerator;
        long den=denominator;
        if(numerator<0){
            num=Math.abs(num);
            minus++;
        }
        if(denominator<0){
            den=Math.abs(den);
            minus++;

        }
        if(minus%2==1){
            sb.append("-");
        }
        //计算整数部分
        if(num>=den){
            sb.append(num/den);
            if(num%den==0){
                return sb.toString();
            }else {
                sb.append(".");
                num=(num%den)*10;
            }
        }else {
            sb.append("0.");
            num*=10;
        }
        //计算小数部分
        StringBuilder sb2=new StringBuilder();
        int index=0;long a;long mod=num;
        Map<Long,Integer> modMap=new HashMap<>();
        modMap.put(mod/10,index);
        while (num!=0){
            a=num/den;
            sb2.append(a);
            mod=num%den;
            if(modMap.containsKey(mod)){
                index=modMap.get(mod);
                break;
            }else {
                index++;
                modMap.put(mod,index);
            }
            num=mod*10;
        }
        if(num!=0){
            sb2.insert(index,'(').append(')');
        }
        return sb.toString()+sb2.toString();
    }

    public int uniquePaths(int m, int n) {
        if(m==1||n==1)return 1;
        int mount=m+n-2;
        long time=1;
        int temp=m>n?(n-1):(m-1);
        for (int i=0;i<temp;i++){
            time*=(mount-i);
            time/=(i+1);
        }
        return (int)time;
    }

    public int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;//因为带符号整数的范围为-2^n~2^n-1，故存在一种特殊情况

        //取两数的绝对值
        long m = Math.abs((long)dividend), n = Math.abs((long)divisor), res = 0;
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;//注意此处异或的作用
        if (n == 1) return sign == 1 ? (int)m :(int) -m;

        while (m >= n) {
			long t = n, p = 1;
            while (m >= (t << 1)) {
                p <<= 1;
                t <<= 1;
            }
            res += p;
            m -= t;
        }

        return sign > 0 ?(int) res :(int) -res;

    }

}
